import java.util.Stack;

/**
 * Created by L.jp
 * Description:输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所
 * 有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但
 * 4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
 * User: 86189
 * Date: 2021-12-25
 * Time: 10:31
 */
//借助一个辅助栈来判断出栈序列，实际就是模拟栈的弹出，此法为模拟法
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA==null || popA==null || pushA.length==0 || popA.length==0 || pushA.length!=popA.length){
            return false;
        }
        //就像我们在平时判断一样，总需要借助一个栈来辅助判断
        Stack<Integer> helper=new Stack<>();
        int i=0;
        int j=0;
        for(;i<pushA.length;i++){
            //遍历入栈序列，将他们加入辅助栈
            helper.push(pushA[i]);
            //同时还要判断当辅助栈为非空时，辅助栈的栈顶元素跟当前出栈序列数组的元素是不是一样，如果一样就要让辅助栈弹出这个元素，继续判断出栈数组的下一个元素
            while(!helper.isEmpty() && helper.peek()==popA[j]){
                helper.pop();
                j++;
            }
        }
        //走到这里，说明入栈数组遍历完了，同时出栈数组也为空了，说明这个出栈数组的序列是满足该栈的弹出顺序的，如果最后栈不为空，说明不符合
        //直接返回栈是否为空的真值
        return helper.isEmpty();

    }
}
